//#include "chain_table.h"
#include "undigraph.h"

#include <iostream>
using std::cout;
using std::endl;
using std::cin;

void test1();
void test2();
void solution();

int main()
{
    //test1();
    //test2();
    solution();

    return 0;
}

void solution()
{
    // 输入
    int n = 0;
    int m = 0; 
    int s = 0;
    int t = 0;
    cin >> n >> m >> s >> t;

    undigraph g(n);
    int opcode = 0;
    int operand1 = 0;
    int operand2 = 0; 
    for (int i = 0; i < m; ++i)
    {
        cin >> opcode >> operand1 >> operand2;
        switch (opcode)
        {
            case 0:
            {
                // 插入边
                g.insert(operand1, operand2);
                break;
            }
            case 1:
            {
                // 删除边
                g.erase(operand1, operand2);
                break;
            }
            default:
            {
                break;
            }
        }
    }

    // 输出
    
    // 连通分量
    int num = 0;
    vector<int> sequence;
    g.connected_components_info(num, sequence);
    cout << num << endl;
    for (int i = 0; i < sequence.size(); ++i)
    {
        cout << sequence[i] << " ";
    }
    cout << endl;

    // dfs
    vector<int> vertex_dfs;
    g.DFS(s, vertex_dfs);
    int sz = vertex_dfs.size();
    cout << sz << endl;
    for (int i = 0; i < sz; ++i)
    {
        cout << vertex_dfs[i] << " ";
    }
    cout << endl;

    // bfs
    vector<int> vertex_bfs;
    g.BFS(t, vertex_bfs);
    sz = vertex_bfs.size();
    cout << sz << endl;
    for (int i = 0; i < sz; ++i)
    {
        cout << vertex_bfs[i] << " ";
    }
    cout << endl;

    cout << g.shortest_path_Dijkstra(s, t) << endl;

}

void test2()
{
    undigraph g1(5);

    g1.insert(1, 2);
    g1.insert(1, 3);
    g1.insert(2, 4);
    g1.insert(3, 4);

    // int num = 0;
    // vector<int> min_sequence;
    // g1.connected_components_info(num, min_sequence);
    // for (int i = 0; i < min_sequence.size(); ++i)
    // {
    //     cout << min_sequence[i] << " ";
    // }
    // cout << endl;

    cout << g1.shortest_path_Dijkstra(1, 5) << endl;
    cout << g1.shortest_path_Dijkstra(1, 4) << endl;

}

void test1()
{
    chain_table<int> t1;
    t1.push_back(1);
    t1.push_back(2);
    t1.push_back(3);
    t1.push_back(4);
    t1.push_back(5);
    t1.push_back(6);
    t1.push_back(7);

    t1.erase(2);
    t1.erase(7);
    t1.erase(1);

}